// 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

// 请你找出符合题意的 最短 子数组，并输出它的长度。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

// 硬写

// 执行用时：
// 20 ms
// , 在所有 C++ 提交中击败了
// 93.97%
// 的用户
// 内存消耗：
// 25.8 MB
// , 在所有 C++ 提交中击败了
// 83.22%
// 的用户

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int begin=-1,end=nums.size();
        bool Noup = false;
        // 获取从前往后第一个非升序
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i]>nums[i+1]){
                if(begin != -1){
                    if(nums[begin]==nums[i]){
                        begin = begin;
                        Noup=true;
                        break;
                    }
                    else{
                        begin = i;
                        Noup = true;
                        break;
                    }
                }
                else{
                    begin = i;
                    Noup = true;
                    break;
                }

            }
            else if(begin==-1&& nums[i]==nums[i+1]){
                begin = i;
            }
        }
        // 获取从后往前第一个非升序
        for(int i=nums.size()-1;i>0;i--){
            if(nums[i]<nums[i-1]){
                if(end!=nums.size()){
                    if(nums[end]==nums[i]){
                        end=end;
                        Noup=true;
                        break;
                    }
                    else{
                        end=i;
                        Noup = true;
                        break;
                    }
                }
                else{
                    end=i;
                    Noup = true;
                    break;
                }
            }
            else if(end==nums.size()&&nums[i]==nums[i-1]){
                end = i;
            }
        }
        // 本身为升序，直接输出
        if(Noup==false){
            return 0;
        }
        // 进行确认，如果有大于最小，小于最大，则变更
        int mi=nums[begin],ma=nums[end];
        for(int i=begin;i<=end;i++){
            mi=min(mi,nums[i]);
            ma=max(ma,nums[i]);
        }
        for(int i=0;i<begin;i++){
            if(nums[i]>mi){
                begin = i;
            }
        }
        for(int i=nums.size()-1;i>end;i--){
            if(nums[i]<ma){
                end = i;
            }
        }
        return end-begin+1;

    }
};